import java.util.HashMap;
import java.util.Map;

public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        // int[] nums = new int[]{1,2,11,2,1};
        // System.out.println(test.pivotIndex(nums));

        // int[] nums = new int[]{1, 2, 3, 4};
        // for(int x: test.productExceptSelf(nums)) {
        //     System.out.print(x + " ");
        // }

        int[] nums = new int[]{1,2,3};
        System.out.println(test.subarraySum(nums, 3));
    }

    public int pivotIndex(int[] nums) {
        /**
         * 寻找数组的中心下标
         * */
        // 1 预处理
        int n = nums.length;

        // 2 计算前缀和
        int[] dp = new int[n+1];
        for(int i = 1; i <= n; i++) {
            dp[i] = dp[i-1] + nums[i-1];
        }

        // 3 找中心下标
        for(int i = 1; i <= n; i++) {
            if(dp[n] - dp[i] == dp[i-1]) {
                return i-1;
            }
        }
        return -1;
    }

    public int[] productExceptSelf(int[] nums) {
        /**
         * 除自身以外数组的乘积
         * 思路：因为本题是求除本身以外所有数的乘积，并且不能使用除法
         * 我们可以先计算除本身以外的前缀乘积和后缀乘积，使其相乘即可
         * */
        // 1 预处理
        int n = nums.length;

        // 2 前缀和操作
        int[] front = new int[n];
        front[0] = 1;
        for(int i = 1; i < n; i++) {
            front[i] = front[i-1] * nums[i-1];
        }
        int[] back = new int[n];
        back[n-1] = 1;
        for(int i = n-2; i >= 0; i--) {
            back[i] = back[i+1] * nums[i+1];
        }
        // 3 输出数组
        int[] retArr = new int[n];
        for(int i = 0; i < n; i++) {
            retArr[i] = front[i] * back[i];
        }
        return retArr;
    }

    public int subarraySum1(int[] nums, int k) {
        /**
         * 和为k的子数组
         * 先使用滑动窗口！
         * 由于k值可能为负数，且元素也存在负数，故无法使用滑动窗口
         * 因为我们无法准确进行出窗口（或许可以使用绝对值）
         * */
        // 1 预处理
        int n = nums.length;

        // 2 滑动窗口
        int left = 0;
        int right = 0;
        int count = 0;
        int sum = 0;
        while (right < n) {
            // -1 进窗口
            sum += nums[right];

            // -2 判断
            // -注意：此处由于k可能取值为负数，而我们sum的默认值为0，此时就会一致满足条件
            while(k >= 0 && left <= right && sum >= k) {
                if(sum == k) {
                    count ++;
                }
                sum -= nums[left];
                left ++;
            }
            while(k < 0 && left <= right && sum <= k) {
                if(sum == k) {
                    count ++;
                }
                sum -= nums[left];
                left ++;
            }
            right ++;
        }
        return count;
    }

    public int subarraySum(int[] nums, int k) {
        /**
         * 和为k的子数组
         * 经验：当数组中同时存在正数和负数时，暂时不考虑滑动窗口！
         * 使用前缀和进行操作
         * */
        // 1 预处理
        int n = nums.length;

        // 2 使用前缀和（O(n)的时间复杂度）
        int[] dp = new int[n+1];
        for(int i = 1; i <= n; i++) {
            dp[i] = dp[i-1] + nums[i-1];
        }

        // 3 双重循环枚举
        // 优化：将前缀和使用map进行存储
        Map<Integer, Integer> map = new HashMap<>();
        int count = 0;
        for(int i = 1; i <= n; i++) {
            // -1 i为右边界，先入图左边界，每次入队前一个，避免出现无效组合
            if(map.containsKey(dp[i-1])) {
                map.put(dp[i-1], map.get(dp[i-1]) + 1);
            } else {
                map.put(dp[i-1], 1);
            }
            // -2 查找是否存在，并统计
            int target = dp[i] - k;
            count += map.getOrDefault(target, 0);
        }

        // 4 返回值
        return count;
    }
}
